package com.zyk.leetcode;

import java.util.Arrays;

/**
 * @author zhangsan
 * @date 2021/5/11 9:54
 */
public class C209 {

    // O(N)
    public static int minSubArrayLen(int target, int[] nums) {
        int l = 0, r = 0, N = nums.length, sum = 0, min = Integer.MAX_VALUE;
        while (r < N) {
            while (r < N && sum < target) {
                sum += nums[r++];
            }
            while (sum >= target) {
                min = Math.min(min, r - l);
                sum -= nums[l++];
            }
            /*if (sum >= target) {
                min = Math.min(min, r - l);
            }
            sum -= nums[l++];*/
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }

    // O(n logn)的解
    // 他是根据暴力解优化过来的: 暴力解就是模拟所有位置开头匹配, 时间复杂度O(N^2)
    // 这里, 提前生成一个前缀和数组,  (l~r)的累加和 = sum[r] - sum[l-1](需要注意l-1不能为0),
    // 亦或是我们多用第一位来装0(l~r)累加和 = sum[r+1] - sum[l] 不用做边界判断
    // 然后 i 能组成 <= target的最小子数组数量, 就可以通过二分查找计算
    public static int minSubArrayLen2(int target, int[] nums) {
        int N = nums.length;
        int[] sum = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        int min = Integer.MAX_VALUE;
        for (int l = 0; l <= N; l++) {
            int r = binarySearch(sum, l, N, sum[l] + target);
            if (r != -1)
                min = Math.min(min, r - l);
        }
        return min;
    }

    // 找到在 sum 数组中 >= target 最左位置
    public static int binarySearch(int[] nums, int l, int r, int target) {
        int mostCorrect = -1, m;
        while (l <= r) {
            m = (l + r) >> 1;       // l + ((r - l) >> 1)
            if (nums[m] < target) {
                l = m + 1;
            } else {    // >= target
                mostCorrect = m;
                r = m - 1;
            }
        }
        return mostCorrect;
    }


    // for test
    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 2, 4, 3};
        int target = 7;

        System.out.println(minSubArrayLen(target, nums));
        System.out.println(minSubArrayLen2(target, nums));
    }

}
